import java.util.Stack;

public class Leetcode20 {
    private static final char[][] BRACKETS = {
            {'(', ')'},
            {'[', ']'},
            {'{', '}'},
    };

    public static void main(String[] args) {
        System.out.println(isValid("{[]}"));
    }

    public static boolean isValid(String s) {
        if (s == null) {
            return false;
        }

        if ((s.length() & 1) != 0) {
            return false;
        }

        Stack<Character> stack = new Stack<>();
        for (char aChar : s.toCharArray()) {
            if (stack.isEmpty()) {
                stack.add(aChar);
                continue;
            }

            boolean flag = false;
            for (char[] bracket : BRACKETS) {
                if (stack.peek() == bracket[0] && aChar == bracket[1]) {
                    stack.pop();
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                stack.add(aChar);
            }
        }

        return stack.isEmpty();
    }

    public boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || c != stack.pop()) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
